//2009/08/25 20:05:53
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

//int xx[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
//int yy[8] = {2, 2, 1, 1, -1, -1, -2, -2};
int xx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int yy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

class KnightsTour
{
public:
    int visitedPositions(vector <string> board)
    {
        //memset(used, false, sizeof(used));
        int ret = 0;
        for (int i=0; i<board.size(); i++)
            for (int j=0; j<board[i].size(); j++)
                if (board[i][j] == 'K')
				{
                    ret = count(i, j, board);
					break;
				}
        return ret;
    }
    int count(int x, int y, vector<string>& b)
    {
		cout << "x: " << x << ", y: " << y << endl;
        //used[x][y] = true;
		b[x][y] = '*';
        int idx = next2go(x, y, b);
        if (idx == -1) return 1;
        return 1 + count(x+xx[idx], y+yy[idx], b);
    }
    int next2go(int x, int y, vector<string>& b)
    {
        int ret = -1;
        int mmin = 10;
        for (int i=0; i<8; i++)
        {
            int xtemp = x + xx[i];
            int ytemp = y + yy[i];
            if (inBound(xtemp, ytemp) && b[xtemp][ytemp] != '*')
            {
                if (mmin > accessibility(xtemp, ytemp, b) && accessibility(xtemp, ytemp, b) >=0)
                {
                    ret = i;
                    mmin = accessibility(xtemp, ytemp, b);
                }
            }
        }
		//cout << "mmin: " << mmin << endl;
        return ret;
    }
    int accessibility(int x, int y, vector<string>& b)
    {
        int sum = 0;
        for (int i=0; i<8; i++)
        {
            int xtemp = x + xx[i];
            int ytemp = y + yy[i];
            if (inBound(xtemp, ytemp) && b[xtemp][ytemp] != '*')
                sum ++;
        }
		//cout << "Sum: " << sum << endl;
        return sum;
    }
    bool inBound(int x, int y)
    {
        if (x>=0 && x<8 && y>=0 && y<8) return true;
        return false;
    }
private:
    //bool used[8][8];
};
